//
// Created by Administrator on 2021/7/20.
//

//给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格0 变成1 。
//返回执行此操作后，grid 中最大的岛屿面积是多少？
//岛屿 由一组上、下、左、右四个方向相连的1 形成。
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/making-a-large-island
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <unordered_set>
#include <numeric>

using namespace std;

class Solution {
private:
    const vector<vector<int>> movements{{1,  0},
                                        {-1, 0},
                                        {0,  1},
                                        {0,  -1}};
public:
    /**
     * 最暴力：尝试把每个0变成1 看看哪个能获得最大岛屿 大概率会超时
     * @param grid
     * @return
     */
    int largestIsland(vector<vector<int>> &grid) {
        int ans = 0;
        int n = (int) grid.size();
        bool allLand = true;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    allLand = false;
                    grid[i][j] = 1;
                    ans = max(ans, curMaxIsland(grid));
                    grid[i][j] = 0;
                }
            }
        }
        return allLand ? n * n : ans;
    }

    /**
     * 当前情况下 最大的岛屿面积
     * @param grid
     * @return
     */
    int curMaxIsland(vector<vector<int>> &grid) {
        int n = (int) grid.size();
        int ans = 0;
        vector<vector<bool>> seen(n, vector<bool>(n, false));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    ans = max(ans, BFS(grid, seen, i, j));
                }
            }
        }
        return ans;
    }

    /**
     * 一块陆地所属的岛屿面积
     * @param grid
     * @param seen
     * @param i
     * @param j
     * @return
     */
    int BFS(vector<vector<int>> &grid, vector<vector<bool>> &seen, int i, int j) {
        int n = (int) grid.size();
        queue<pair<int, int>> q;
        q.emplace(i, j);
        int area = 1;
        seen[i][j] = true;
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            auto r = p.first, c = p.second;
            for (int k = 0; k < 4; ++k) {
                int nr = r + movements[k][0];
                int nc = c + movements[k][1];
                if (nr >= 0 and nr < n and nc >= 0 and nc < n and grid[nr][nc] == 1 and not seen[nr][nc]) {
                    q.emplace(nr, nc);
                    seen[nr][nc] = true;
                    ++area;
                }
            }
        }
        return area;
    }
    // 果然超时
};

class Solution2 {
private:
    const vector<vector<int>> movements{{1,  0},
                                        {-1, 0},
                                        {0,  1},
                                        {0,  -1}};
public:
    /**
     * 两次遍历 第一次对原始矩阵 第二次尝试将每个0变成1
     * @param grid
     * @return
     */
    int largestIsland(vector<vector<int>> &grid) {
        int ans = 0;
        int n = (int) grid.size();
        vector<vector<bool>> seen(n, vector<bool>(n, false)); // 搜索过程标记矩阵
        /// 初始状态先搜索一遍
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1 and not seen[i][j]) {
                    ans = max(ans, BFS(grid, seen, i, j));
                }
            }
        }
        //  对于每个0 变为 1后 再搜索一次
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    grid[i][j] = 1;
                    seen = vector<vector<bool>>(n, vector<bool>(n, false)); //重置标记矩阵
                    ans = max(ans, BFS(grid, seen, i, j));
                    grid[i][j] = 0;
                }
            }
        }
        return ans;

    }

    /**
     * BFS 求一个1所属的岛屿的总面积   DFS肯定也可以
     * @param grid 网格
     * @param i 横坐标
     * @param j 纵坐标
     * @return
     */
    int BFS(vector<vector<int>> &grid, vector<vector<bool>> &seen, int i, int j) {
        int n = (int) grid.size();
        queue<pair<int, int>> q;
        q.emplace(i, j);
        int area = 1;
        seen[i][j] = true;
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            auto r = p.first, c = p.second;
            for (int k = 0; k < 4; ++k) {
                int nr = r + movements[k][0];
                int nc = c + movements[k][1];
                if (nr >= 0 and nr < n and nc >= 0 and nc < n and grid[nr][nc] == 1 and not seen[nr][nc]) {
                    q.emplace(nr, nc);
                    seen[nr][nc] = true;
                    ++area;
                }
            }
        }
        return area;
    }
    // 依旧超时
};

class Solution3 {
private:
    const int movements[4][2]{
            {1,  0},
            {-1, 0},
            {0,  1},
            {0,  -1}
    };
//    const vector<vector<int>> movements{{1,  0},
//                                        {-1, 0},
//                                        {0,  1},
//                                        {0,  -1}};
public:
    int largestIsland(vector<vector<int>> &grid) {
        int ans = 0;
        int n = (int) grid.size();
        unordered_map<int, int> color2Area; // 记录每块颜色陆地对应的面积
        /// 初始状态先搜索一遍
        int color = 2; // 原始的grid是0 1 那么涂色从2开始
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    int curArea = DFS(grid, i, j, color);
                    ans = max(ans, curArea);
                    color2Area[color] = curArea;
                    ++color;
                }
            }
        }
        /**
         * 找到网格里现在剩下的0，观察这个0四周的岛屿颜色和面积，可以得到将这块0变成岛屿后，可以获得的新岛屿的面积
         * 新岛屿面积为周围不同的岛屿面积之和+1
         */
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    vector<int> neighborArea{};
                    unordered_set<int> neighbor;
                    for (auto movement : movements) {
                        int ni = i + movement[0];
                        int nj = j + movement[1];
                        if (ni >= 0 and ni < n and nj >= 0 and nj < n and grid[ni][nj] > 0) {
                            if (!neighbor.count(grid[ni][nj])) {
                                neighborArea.push_back(color2Area[grid[ni][nj]]);
                                neighbor.insert(grid[ni][nj]);
                            }
                        }
                    }
                    ans = max(ans, accumulate(neighborArea.begin(), neighborArea.end(), 0) + 1);
                }
            }
        }


        return ans;
    }

    /**
    * BFS 求一个1所属的岛屿的总面积  并被这块岛屿涂色
    * @param grid 网格
    * @param i 横坐标
    * @param j 纵坐标
    * @return
    */
    int BFS(vector<vector<int>> &grid, int i, int j, int color) {
        int n = (int) grid.size();
        queue<pair<int, int>> q;
        q.emplace(i, j);
        grid[i][j] = color; // 初始点涂色
        int area = 1;
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            auto r = p.first, c = p.second;
            for (auto movement : movements) {
                int nr = r + movement[0];
                int nc = c + movement[1];
                if (nr >= 0 and nr < n and nc >= 0 and nc < n and grid[nr][nc] == 1) {
                    q.emplace(nr, nc);
                    grid[nr][nc] = color;
                    ++area;
                }
            }
        }
        return area;
    }

    int DFS(vector<vector<int>> &grid, int i, int j, int color) {
        int area = 1;
        int n = (int) grid.size();
        grid[i][j] = color;
        for (auto movement : movements) {
            int ni = i + movement[0];
            int nj = j + movement[1];
            if (ni >= 0 and ni < n and nj >= 0 and nj < n and grid[ni][nj] == 1) {
                area += DFS(grid, ni, nj, color);
            }
        }
        return area;
    }

};

class Solution4 { // 优秀题解
public:
    int areaNum = 1;
    vector<int> areaSize;

    /**
     * DFS 涂色
     * @param i
     * @param j
     * @param row
     * @param low
     * @param grid
     * @return
     */
    int landArea(int i, int j, int row, int low, vector<vector<int>> &grid) {
        if (i < 0 || i >= row) {
            return 0;
        }
        if (j < 0 || j >= low) {
            return 0;
        }
        if (grid[i][j] != 1) {
            return 0;
        }

        grid[i][j] = areaNum;
        return 1 + landArea(i, j - 1, row, low, grid) + landArea(i, j + 1, row, low, grid) +
               landArea(i - 1, j, row, low, grid) + landArea(i + 1, j, row, low, grid);
    }

    /**
     * 得到原始状态下  各个岛屿的面积
     * @param m
     * @param n
     * @param grid
     */
    void getLandAreas(int m, int n, vector<vector<int>> &grid) {
        int land = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    areaNum++;
                    land = landArea(i, j, m, n, grid);
                    areaSize.push_back(land);
                }
            }
        }
    }

    // ？？ 这么暴力
    int maxAreaOfIsland(int m, int n, int i, int j, vector<vector<int>> &grid) {
        int land = 1;
        int up = 0;
        if (i - 1 >= 0 && grid[i - 1][j] > 0) {
            up = grid[i - 1][j];
            land += areaSize[up - 2];
        }

        int down = 0;
        if (i + 1 < m && grid[i + 1][j] > 0 && grid[i + 1][j] != up) {
            down = grid[i + 1][j];
            land += areaSize[down - 2];
        }

        int left = 0;
        if (j - 1 >= 0 && grid[i][j - 1] > 0 && (grid[i][j - 1] != up) && (grid[i][j - 1] != down)) {
            left = grid[i][j - 1];
            land += areaSize[left - 2];
        }

        if (j + 1 < n && grid[i][j + 1] > 0 && (grid[i][j + 1] != up) && (grid[i][j + 1] != down) &&
            (grid[i][j + 1] != left)) {
            land += areaSize[grid[i][j + 1] - 2];
        }

        return land;

    }

    /**
     * 入口
     * @param grid
     * @return
     */
    int largestIsland(vector<vector<int>> &grid) {
        int m = (int) grid.size();
        if (m == 0) {
            return 0;
        }
        int n = (int) grid[0].size();
        if (n == 0) {
            return 0;
        }
        areaNum = 1;
        areaSize.clear();
        getLandAreas(m, n, grid);
        int maxLand = 0;
        int land = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    land = maxAreaOfIsland(m, n, i, j, grid);
                    maxLand = maxLand > land ? maxLand : land;
                }
            }
        }
        if (maxLand == 0) {
            maxLand = m * n;
        }
        return maxLand;
    }
};

int main() {
    vector<vector<int>> grid{{0, 0, 0, 0, 0, 0, 0},
                             {0, 1, 1, 1, 1, 0, 0},
                             {0, 1, 0, 0, 1, 0, 0},
                             {1, 0, 1, 0, 1, 0, 0},
                             {0, 1, 0, 0, 1, 0, 0},
                             {0, 1, 0, 0, 1, 0, 0},
                             {0, 1, 1, 1, 1, 0, 0}};

    Solution3 solution;
    cout << solution.largestIsland(grid) << endl;
    return 0;
}